package com.fengye.algorithms.leecode;

import com.fengye.algorithms.leecode.common.Node;

import java.util.LinkedList;

/**
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author fengye
 * @Date 2023/4/14 9:18
 **/
public class PopulatingNextRightPointersInEachNode116 {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        Node node11 = new Node(11);
        Node node12 = new Node(12);
        Node node13 = new Node(13);
        Node node14 = new Node(14);
        Node node15 = new Node(15);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        node5.left = node10;
        node5.right = node11;
        node6.left = node12;
        node6.right = node13;
        node7.left = node14;
        node7.right = node15;


        new PopulatingNextRightPointersInEachNode116().connect2(node1);
    }

    /**
     * 通过根节点来处理
     * @param root
     * @return
     */
    public Node connect2(Node root) {
        if(root == null) {
            return root;
        }

        // 从根节点开始
        Node leftMost = root;
        while (leftMost.left != null) {
            Node head = leftMost;
            while (head != null) {
                // 左节点连接右节点
                head.left.next = head.right;
                // head不是当前这一层最后一个节点
                if(head.next != null) {
                    head.right.next = head.next.left;
                }
                head = head.next;
            }
            // 取每一层的最左节点
            leftMost = leftMost.left;
        }
        return root;
    }

    /**
     * 通过叶子节点来处理
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }
        LinkedList<Node> queue = new LinkedList<Node>();
        Node current = null;
        //将根节点入队
        queue.offer(root);
        int count = 1;
        int n = 1;
        while(!queue.isEmpty()) {
            //出队队头元素并访问
            current = queue.poll();
            System.out.print(current.val +"("+count+", "+n+")-->");
            // 利用完全二叉树的特性，每一层最后一位+1 == 2的幂次
            if(!(((count+1) & count) == 0) && !queue.isEmpty()) {
                current.next = queue.peek();
            }
            //如果当前节点的左节点不为空入队
            if(current.left != null){
                queue.offer(current.left);
            }
            //如果当前节点的右节点不为空，把右节点入队
            if(current.right != null){
                queue.offer(current.right);
            }
            count++;
        }
        return root;
    }

    public void levelIterator(Node root) {
        if(root == null) {
            return ;
        }
        LinkedList<Node> queue = new LinkedList<Node>();
        Node current = null;
        //将根节点入队
        queue.offer(root);
        boolean lastLevel = false;
        while(!queue.isEmpty()) {
            boolean flag = false;
            if((queue.size() & 1) == 0) {
                flag = true;
            }

            if(lastLevel && queue.size() > 1) {
                flag = true;
            }
            //出队队头元素并访问
            current = queue.poll();
            System.out.print(current.val +"-->");
            if(flag) {
                current.next = queue.peek();
            }
            //如果当前节点的左节点不为空入队
            if(current.left != null){
                lastLevel = false;
                queue.offer(current.left);
            } else {
                lastLevel = true;
            }
            //如果当前节点的右节点不为空，把右节点入队
            if(current.right != null){
                lastLevel = false;
                queue.offer(current.right);
            } else {
                lastLevel = true;
            }
        }

    }
}
